package q793_preimageSizeFZF;

public class Solution {
    /*
    二分查找思想：如果要找后缀为k个0的阶乘有多少个
    可以转化为后缀为k + 1个0的阶乘不超过多少个 - 后缀为k个0的阶乘不超过多少个
     */
    public int preimageSizeFZF(int k) {
        return (int) (helper(k + 1) - helper(k));
    }

    private long helper(int k) {
        long r = 5L * k, l = 0;
        while (r >= l) {
            long mid = (l + r) / 2;
            if (zeroCount(mid) < k) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return r + 1;
    }

    private int zeroCount(long n) {
        int ans = 0;
        while (n > 0) {
            ans += n / 5;
            n /= 5;
        }
        return ans;
    }
}
